1. Field of the Invention
The present invention relates to a motion vector detecting circuit, and more particularly to a motion vector detecting circuit for detecting a motion vector by block matching between a prediction target image and a reference image in moving image coding using the motion compensation prediction.
2. Related Background Art
There are major methods for obtaining a motion vector by block matching, for example the full search, the three-step search, etc. as described in "INTERFACE," pp 138, Aug. 1992.
The computational complexity is examined in the following for the conventional motion vector detecting methods.
In the following description, "sub" means subtraction, "add" addition, and "ops" computational complexity.
Also, it is assumed that a block is a square block in the size of 16.times.16 pixels, a search range of motion vector is a square region between -15 and +15 both in the horizontal direction and in the vertical direction, the accuracy of motion vector is one pixel unit, and a prediction error is a sum of absolute values of differences between pixel values.
1. Full search
(1) A process for obtaining a prediction error PE using all pixels in block is executed for all candidate blocks of 961 (i.e., 31.sup.2).
(2) An optimum motion vector is a motion vector to a candidate block giving a minimum prediction error PE.
The above process requires the following computational complexity for block matching.
Computation of prediction error PE: 256 (sub)+255 (add)=511 ops
Comparison between prediction error PE and minimum: 1 ops
For all candidate blocks of 961, necessary computation is: EQU (511+1).times.961=492032 ops.
2. 3-step search
(1) A process for obtaining a prediction error PE using all pixels in block is executed for candidate blocks corresponding to motion vectors (4 m, 4 n).
Here, m and n are integers between -3 and +3.
(2) A minimum value of the prediction errors PE obtained in (1) is defined as MIN PE and a motion vector giving MIN PE as (x, y). Then, a process for obtaining a prediction error PE using all pixels in block is conducted for eight candidate blocks corresponding to motion vectors (x-2, y-2), (x, y-2), (x+2, y-2), (x-2, y), (x+2, y), (x-2, y+2), (x, y+2), and (x+2, y+2). If PE&lt;MIN PE then it is set as MIN PE=PE.
(3) A motion vector giving MIN PE in (2) is defined as (x, y). Then, a process for obtaining a prediction error PE using all pixels in block is conducted for eight candidate blocks corresponding to motion vectors (x-1, y-1), (x, y-1), (x+1, y-1), (x-1, y), (x+1, y), (x-1, y+1), (x, y+1), and (x+1, y+1). If PE&lt;MIN PE then it is set as MIN PE=PE.
(4) A motion vector giving MIN PE in (3) is determined as an optimum motion vector.
The above process requires the following computational complexity for block matching.
Computation of prediction error PE: 511 ops
Comparison between prediction error PE and minimum MIN PE: 1 ops
Number of prediction errors PE obtained in (1): 7.times.7=49
Number of prediction errors PE obtained in (2): 8
Number of prediction errors PE obtained in (3): 8
Thus, the total computation is as follows: EQU (511+1).times.(49+8+8)=33280 ops
3. 2-step search
(1) A process for obtaining a prediction error PE using all pixels in block is executed for candidate blocks corresponding to motion vectors (3 m, 3 n).
Here, m and n are integers between -5 and +5.
(2) A minimum value of prediction errors PE obtained in (1) is defined as MIN PE and a motion vector giving MIN PE as (x, y). Then, a process for obtaining a prediction error PE using all pixels in block is conducted for eight candidate blocks corresponding to motion vectors (x-1, y-1), (x, y-1), (x+1, y-1), (x-1, y), (x+1, y), (x-1, y+1), (x, y+1), and (x+1, y+1). If PE&lt;MIN PE then it is set as MIN PE=PE.
(3) A motion vector giving MIN PE in (2) is determined as an optimum motion vector.
The above process requires the following computational complexity for block matching.
Computation of prediction error PE: 511 ops
Comparison between prediction error PE and minimum MIN PE: 1 ops
Number of prediction errors PE obtained in (1): 11.times.11=121
Number of prediction errors PE obtained in (2): 8
Thus, the total computation is as follows: EQU (511+1).times.(121+8)=66048 ops
As described above, the full search, however, requires the massive amounts of computational complexity for block matching.
Also, the 3-step search and the 2-step search cannot obtain a correct motion vector, because the search is limited to some candidate blocks. Thus, the quality of reproduced image is extremely degraded in the searches as compared with the full search.